/**
 * 归并排序
 * 
 * 基本思想
 * 归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略
 * （分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
 * 实际上就是将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
 * 
 * 具体步骤
 * 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
 * 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
 * 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
 * 4. 重复步骤 3 直到某一指针达到序列尾；
 * 5. 将另一序列剩下的所有元素直接复制到合并序列尾。
 * 
 * 最好时间复杂度：O(NlogN)
 * 最坏时间复杂度：O(NlogN)
 * 平均时间复杂度：O(NlogN)
 * 空间复杂度：O(N)
 * 
 * 稳定排序:是
 * 原地排序:是
*/
#include <stdlib.h>
#include "../include/common.h"

#define MAXSIZE 20

// 归并排序，并把最后的结果存放到list1里
void merging(ElementType *list1, int list1_size, ElementType *list2, int list2_size) {
    int i, j, k, m;
    ElementType temp[MAXSIZE];
    i = j = k = 0;
    // 依次比较两个序列的元素，按顺序加入有序列表 temp
    while (i < list1_size && j < list2_size) {
        if (list1[i] < list2[j]) {
            temp[k++] = list1[i++];
        }
        else {
            temp[k++] = list2[j++];
        }
    }
    // 将较长序列直接加入有序序列
    while (i < list1_size) {
        temp[k++] = list1[i++];
    }
    while (j < list2_size) {
        temp[k++] = list2[j++];
    }

    // 复制序列
    for (m = 0; m < (list1_size + list2_size); m++) {
        list1[m] = temp[m];
    }
}

void MergeSort(ElementType arr[], int len) {
    if (len > 1) {
        ElementType *list1 = arr;
        int list1_size = len / 2;
        ElementType *list2 = arr + len / 2;
        int list2_size = len - list1_size;
        MergeSort(list1, list1_size);
        MergeSort(list2, list2_size);
        merging(list1, list1_size, list2, list2_size);
    }
}


void MergeSort_Iterative(int k[],int n) {
    int i,next,left_min,left_max,right_min,right_max;
    //开辟一个与原来数组一样大小的空间用来存储用
    int *temp = (int *)malloc(n * sizeof(int));
    //逐级上升，第一次比较2个，第二次比较4个，第三次比较8个。。。
    for(i=1; i<n; i*=2) {
        //每次都从0开始，数组的头元素开始
        for(left_min=0; left_min<n-i; left_min = right_max) {
            right_min = left_max = left_min + i;
            right_max = left_max + i;
            //右边的下标最大值只能为n
            if(right_max>n) {
                right_max = n;
            }
            //next是用来标志temp数组下标的，由于每次数据都有返回到K，
            //故每次开始得重新置零
            next = 0;
            //如果左边的数据还没达到分割线且右边的数组没到达分割线，开始循环
            while(left_min<left_max&&right_min<right_max) {
                if(k[left_min] < k[right_min]) {
                    temp[next++] = k[left_min++];
                }
                else {
                    temp[next++] = k[right_min++];
                }
            }
            //上面循环结束的条件有两个，如果是左边的游标尚未到达，那么需要把
            //数组接回去，可能会有疑问，那如果右边的没到达呢，其实模拟一下就可以
            //知道，如果右边没到达，那么说明右边的数据比较大，这时也就不用移动位置了

            while(left_min < left_max)  {
                //如果left_min小于left_max，说明现在左边的数据比较大
                //直接把它们接到数组的min之前就行
                k[--right_min] = k[--left_max]; 
            }
            while(next>0) {
                //把排好序的那部分数组返回该k
                k[--right_min] = temp[--next]; 
            }
        }
    }
}

/* ----------------------------------------- */

void merge(ElementType arr[], int low, int mid, int high){
    ElementType *A = (ElementType *) malloc (MAXSIZE * sizeof(ElementType));
    int i, j, k;
    for (i=low; i<high; i++)
        A[i] = arr[i];
    // 选取子序列中更小的元素加入有序序列
    for (i=low, j=mid+1, k=i; i<mid && j<=high; k++){
        if (A[i] <= A[j])
            arr[k] = A[i++];
        else 
            arr[k] = A[j++];
    }
    // 将较长序列剩余部分直接加入有序序列
    while (i <= mid)
        arr[k++] = A[i++];
    while (j <= high)
        arr[k++] = A[j++];
}


void MergeSort2(ElementType arr[], int low, int high){
    // int low = 0, hight = len -1;
    if (low < high){
        int mid = (low + high) / 2;
        MergeSort2(arr, low, mid);
        MergeSort2(arr, mid+1, high);
        merge(arr, low, mid, high);
    }
}


/**
 * 改进：
 *  先利用插入排序获得较长的有序子序列，然后再两两归并（改进后的归并亦是稳定的，因为插入排序是稳定的）
*/